Digital signatures are widely used in practice and play a role similar to the role of the usual hand-written signature. The advantages of the digital signature lie in the fact that its authenticity is easy to verify, its falsification is very difficult, and furthermore, the digital signature can easily be transmitted via telecommunication channels. Systems utilizing digital signature operate on data that are stored on a suitable material storage media and admit digital representation.
In the RSA-scheme, called so by the names of its inventors (R. L. Rivest, A. Shamir, L. M. Adleman, Cryptographic Communications System and Method, U.S. Pat. No. 4,405,829, 20 Sep. 1983), data are represented by integers from a certain residue system modulo an integer N, called the RSA-module. One usually takes the integers from 0 to N−1 as a residue system. For the sake of definiteness, notions related to the RSA-scheme (A. J. Menezes, P. C. Van Oorshot, S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997, p. 285, 433) may be equipped by the prefix RSA, for example: RSA-signature, RSA-encryption, RSA-key, RSA-exponent, etc.
The data S satisfies a digital RSA-signature property related to the data M with respect to the RSA-key with module N and exponent E, or in other words, S is a digital RSA-signature on the data M, if M≡SE (mod N), where the RSA-key means arbitrary data determining the module and exponent, and the formula A≡B (mod N) means that A and B are congruent modulo N, i.e., the integer (A−B) is divisible by N without a remainder.
A digital RSA-signature on the data M can be made by a RSA-encryption of the data M, when a signer secret RSA-key corresponding to a public RSA-key with module N and exponent E is used as an encryption key. Here, the RSA-encryption means a processing of the data X resulting in obtaining a data Y satisfying the relation Y≡XC (mod N), where C and N are the exponent and module of the encryption RSA-key, respectively. The correspondence of two RSA-keys means the possibility of verifying the digital RSA-signature made by one RSA-key with the help of the other RSA-key, or what is the same, the possibility of decryption of the data encrypted by one key with the help of the other key. The correspondence of the RSA-keys with exponents A and B and module N is ensured by the condition A·B≡1 (mod φ(N)), where φ(N) is the number of the residues coprime to N.
However, making a digital RSA-signature on the initial data M by directly RSA-encryption the initial data with the help of the signer secret RSA-key does not ensure the privacy of the suppliers, since the initial data to be signed are accessible to the signer when making the signature. This is clarified in the article D. Chaum, Blind signatures for untraceable payments, Advanced in Cryptology—Proceedings of Crypto 82, 1983, p. 199-203, where Chaum introduces the concept of blind digital signature, which is intended for overcoming this deficiency.
Known in the prior art is a method for making a blind digital RSA-signature (D. Chaum, Blind Signature Systems, U.S. Pat. No. 4,759,063, 19 Jul. 1988), in which the supplier wishing to obtain a digital RSA-signature on the initial data M chooses the randomized blinding key R and develops blinded data M′ by the formula M′≡RE·M (mod N), where E is the exponent and N is the module of the public RSA-key. The blinded data are given to the signer, who returns a digital RSA-signature S′ on the blinded data to the supplier. The supplier completes obtaining the digital RSA-signature S on the initial data by unblinding the obtained digital RSA-signature on the blinded data with the help of the formula S≡S′·R−1 (mod N). The known method ensures untraceability, i.e. practical impossibility for the signer who obtains afterwards signatures on numerous initial data, to establish the correspondence between these signatures and the processed blinded data. However, the known method does not allow to obtain a blind digital RSA-signature without knowing the kind of signature in advance, since the exponent E of the public key determining the kind of signature is used for developing the blinded data.
Known in the prior art is a method for making a blind unanticipated digital RSA-signature (D. Chaum, Blind Unanticipated Signature Systems, U.S. Pat. No. 4,759,064, 19 Jul. 1988), which is the closest analog of the present invention and is chosen by the applicant as the prototype. In this method, a collection of admissible public RSA-exponents E1 . . . , Ek and a collection of data (g1 . . . gu) called generators are used. For each generator gj, digital RSA-signatures Si,j corresponding to each of the admissible public RSA-exponents Ei are published. The supplier takes the collection (k1 . . . ,ku) as the randomized blinding key R and develops blinded data M′ by the formula M′=M·1k1· . . . ·guku mod N), where N is the module of the public RSA-key. The blinded data M′ is given to the signer, who chooses the kind of signature, i.e., chooses that admissible public RSA-exponent Ei to which the obtained digital RSA-signature corresponds. The digital RSA-signature S′ on the blinded data corresponding to the chosen public RSA-exponent Ei, together with the information on the chosen public RSA-exponent Ei, is given to the supplier. The supplier obtains the digital RSA-signature S on the initial data by unblinding the RSA-signature S′ with the help of the formula S≡S′·Si,1−k1· . . . ·Si,u−ku (mod N).
In the known method for making a blind unanticipated digital RSA-signature, the untraceability is ensured by certain properties of the generators with respect to secret RSA-keys, in which connection testing the suitability of the generators by the “cut and choose” method is used. The signature in the known method is called unanticipated because at the moment of giving the blinded data to the signer, the supplier does not know the kind of signature, i.e., the public RSA-exponent, to which the signature to be made will correspond.
The deficiencies of the known method are in that the number of kinds of the obtained RSA-signature is limited decreasing its unanticipatability, the probability of an error increases in making the signature, and the number of the kinds of signature slows down the rate of making the signature. The indicated deficiencies are caused by the necessity to perform the unblinding with the help of data which volume grows proportionally to the number of the kinds of signature, and in turn, the data themselves require additional resources and time for their storage and processing. Moreover, the known method has an insufficient trustworthiness of the untraceability, since the suitability of the data communicated by the signer, in particular, of the generators, is verified by a third party, and not directly by the supplier.
Known in the prior art is an apparatus for making a blind digital RSA-signature (D. Chaum, Blind Signature Systems, U.S. Pat. No. 4,759,063, 19 Jul. 1988). However, this apparatus is not sufficient for making a blind unanticipated digital RSA-signature.
Known in the prior art is an apparatus for making a blind unanticipated digital RSA-signature (D. Chaum, Blind Unanticipated Signature Systems, U.S. Pat. No. 4,759,064, 19 Jul. 1988), which is most close to the claimed apparatus and is chosen by the applicant as the prototype. The known apparatus consists of a blinding key choice unit including a random-number generator, a blinding unit, a signature unit, and an unblinding unit. The blinding unit has an initial data input and a blinding key input and comprises a modular exponentiator whose module input is connected to the module input of the blinding unit, and whose exponent input is connected to the blinding key input of the blinding unit. The signature unit has a secret key input and a signing data input connected with an output of the blinding unit. The unblinding unit has a module input, an exponent input, a blinding key input, an unblinding data input connected with an output of the signature unit, and an output for outputting the digital RSA-signature on the initial data.
The deficiencies of the known apparatus are in that it does not allow to use an unlimited number of kinds of signature when making a blind digital RSA-signature, which decreases the unanticipatability of the RSA-signature to be made, and in the case of employment of this apparatus, the probability of errors when making the signature increases and the number of kinds of signature slows down the rate of making the signature, which is caused by the necessity to enter certain data into the unblinding unit, and a procedure of searching these data requires time growing proportionally to the number of kinds of signature.